Dance Mooves¶

Farmer John 的奶牛们正在炫耀她们的最新舞步！

最初，所有的 $N$ 头奶牛（$2≤N≤105$）站成一行，奶牛 $i$ 排在其中第 $i$ 位。舞步序列给定为 $K$ 个位置对 $(a1,b1),(a2,b2),…,(aK,bK)$。在舞蹈的第 $i=1…K$ 分钟，位置 $ai$ 与 $bi$ 上的奶牛交换位置。同样的 $K$ 次交换在第 $K+1…2K$ 分钟发生，在第 $2K+1…3K$分钟再次发生，以此类推，无限循环。换言之，

• 在第 $1$ 分钟，位置 $a_1$ 与 $b_1$ 上的奶牛交换位置。
• 在第 $2$分钟，位置 $a_2$ 与 $b_2$ 上的奶牛交换位置。
• ……
• 在第 $K$ 分钟，位置 $a_K$ 与 $b_K$ 上的奶牛交换位置。
• 在第 $K+1$ 分钟，位置 $a_1$ 与 $b_1$ 上的奶牛交换位置。
• 在第 $K+2$ 分钟，位置 $a_2$ 与 $b_2$ 上的奶牛交换位置。
• 以此类推……

对于每头奶牛，求她在队伍中会占据的不同的位置数量。

输入格式（从终端/标准输入读入）：¶

输入的第一行包含 $N$ 和 $K$。以下 $K$ 行分别包含 $(a1,b1)…(aK,bK)$（$1≤ai<bi≤N$）。

输出格式（输出至终端/标准输出）：¶

输出 $N$ 行，第 $i$ 行包含奶牛 $i$ 可以到达的不同的位置数量。

输入样例：¶

1
2
3
4
5

5 4
1 3
1 2
2 3
2 4

输出样例：¶

1
2
3
4
5

4
4
3
4
1

• 奶牛 $1$ 可以到达位置 ${1,2,3,4}$。
• 奶牛 $2$ 可以到达位置 ${1,2,3,4}$。
• 奶牛 $3$ 可以到达位置 ${1,2,3}$。
• 奶牛 $4$ 可以到达位置 ${1,2,3,4}$。
• 奶牛 $5$ 从未移动，所以她没有离开过位置 $5$。

测试点性质：¶

• 测试点 1-5 满足 $N≤100,K≤200$。
• 测试点 6-10 满足 $N≤2000,K≤4000$。
• 测试点 11-20 没有额外限制。